import java.util.HashMap;
import java.util.Map;

public class BinaryTree {
    private static TreeNode root;

    public BinaryTree(){
    }


    /**
     * 插入节点
     * @param val
     */
    public static boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null){
            if(val < cur.val){
                parent = cur;
                cur = cur.left;
            }else if(val > cur.val){
                parent = cur;
                cur = cur.right;
            }else{
                return false;
            }
        }

        if(parent.left == null){
            parent.left = node;
        }else{
            parent.right = node;
        }
        return true;
    }

    /**
     * 查询节点
     * @param val
     */
    public static boolean select(int val){
        if(root == null){
            return false;
        }
        TreeNode cur = root;
        while(cur != null){
            if(val < cur.val){
                cur = cur.left;
            }else if(val > cur.val){
                cur = cur.right;
            }else{
                return true;
            }
        }
        return false;
    }

    /**
     * 删除节点:
     * 1.删除叶子结点,直接置为null
     * 2.删除只有一颗子树的节点,将父节点指向该节点
     * 3.删除有两颗子树的节点
     *
     * @param val
     */
    public static boolean remove(int val){
        if(root == null){
            throw new RuntimeException("树中没有节点,删除失败");
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null){
            if(val < cur.val){
                parent = cur;
                cur = cur.left;
            }else if(val > cur.val){
                parent = cur;
                cur = cur.right;
            }else{
                removeNode(parent,cur);
                return true;
            }
        }
        return false;
    }

    private static void removeNode(TreeNode parent, TreeNode cur) {
        // cur节点是叶子节点,直接将该节点置空
        if(cur.left == null && cur.right == null){
            cur = null;
            return;
        }

        // cur节点有一颗子树
        if(cur.left == null || cur.right == null){
            if(cur == root){
                if(cur.left == null){
                    root = cur.right;
                }else{
                    root = cur.left;
                }
            }else if(cur.left == null){
                if(parent.left == cur){
                    parent.left = cur.right;
                }else{
                    parent.right = cur.right;
                }
            }else{
                if(parent.left == cur){
                    parent.left = cur.left;
                }else{
                    parent.right = cur.left;
                }
            }
            return;
        }

        // cur 节点有两颗子树 找左树最右或者右树最左
        // 左树最右
        TreeNode tmp = cur;
        cur = cur.left;
        while(cur.right != null){
            parent = cur;
            cur = cur.right;
        }
        tmp.val = cur.val;
        if(parent == cur) {
            parent.left = cur.left;
        }else{
            parent.right = cur.left;
        }
    }
}

class Test{
    public static void main(String[] args) {
        BinaryTree.insert(5);
        BinaryTree.insert(4);
        BinaryTree.insert(7);
        BinaryTree.insert(9);
        BinaryTree.insert(6);
        System.out.println(BinaryTree.select(7));
        BinaryTree.remove(7);
        System.out.println(BinaryTree.select(7));


        Map<String,Integer> map  = new HashMap<>();
        map.put("zhangsan",13);
        Integer a = map.get("zhangsan");
        System.out.println(a);





    }
}
